import javax.swing.tree.TreeNode;
import java.util.Enumeration;
import java.util.HashMap;
import java.util.Map;

public class Test1121 {
    /*
解决从中序与后序遍历序列构造二叉树的问题

解题思路：
一、类成员变量定义（后序索引指针、后序数组、中序数组、哈希表idx_map（key=中序遍历元素值，value=中序索引））
二、构造递归函数helper
    1.递归终止条件
    2.取当前子树的根节点
    3.从哈希表中获取根节点在中序中的索引
    4.后序指针前移
    5.构造右左子树（必须先构建右再构建左，post_idx前移后指向的是右子树的根，如果先构建左子树，会错误地把左子树的根当成右子树的根）
    6.返回子树根节点
三、构建入口方法buildTree（初始化全局变量，构建哈希表，启动递归函数）
    */

    int post_idx;
    int[] postorder;
    int[] inorder;
    Map<Integer,Integer> idx_map = new HashMap<Integer,Integer>();

    public TreeNode helper(int in_left, int in_right){
        if(in_left > in_right){
            return null;
        }
        int root_val = postorder[post_idx];
        TreeNode root = new TreeNode() {
            @Override
            public TreeNode getChildAt(int childIndex) {
                return null;
            }

            @Override
            public int getChildCount() {
                return 0;
            }

            @Override
            public TreeNode getParent() {
                return null;
            }

            @Override
            public int getIndex(TreeNode node) {
                return 0;
            }

            @Override
            public boolean getAllowsChildren() {
                return false;
            }

            @Override
            public boolean isLeaf() {
                return false;
            }

            @Override
            public Enumeration<? extends TreeNode> children() {
                return null;
            }
        };
        int index = idx_map.get(root_val);
        post_idx--;
        return root;
    }
    public TreeNode buildTree(int[] inorder,int[] postorder){
        this.postorder = postorder;
        this.inorder = inorder;
        post_idx = postorder.length - 1;

        int idx = 0;
        for(Integer val : inorder){
            idx_map.put(val,idx++);
        }

        return helper(0,inorder.length - 1);
    }
}
